CMU 11642 的课程笔记。Best match模型衡量的是一篇文档与 information need 的匹配程度，与 Exact match模型（匹配／不匹配）相比更注重用户体验，不管有没有匹配 Best match 都会返回文档结果。

这一篇考虑的是 query dependent 的分数，网页打分的依据是文档和查询的相关性分数，也就是信息检索得分(IR score)。有很多理论来计算 IR score，这里主要介绍以下 4 种理论：

向量空间 Vector space retrieval model(VSM)
概率理论 Probabilistic retrieval model(BM25)
统计语言模型 Statistical language model(query likelihood)
推理网络 Inference networks(Indri)

它们的公式其实都和 tf-idf 的公式相似。每个单词－文档组合都有一个tf-idf值。tf 表示此文档中这个单词出现的次数；df 表示含有这个单词的文档的数量。通常如果一个单词在文档中出现次数越多说明这个文档与这个单词相关性越大。但是有的单词太常用了，比如英文里“the”，“a” 在任何一个文档中都会大量出现。idf 就表示一个文档含有此单词的概率的倒数，用来消除常用词干扰。如果某个词或短语在一篇文章中出现的频率 TF 高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。

Document Priors 指与 query 无关的用来评估文档价值的 estimates(query independent)，主要的 document priors 有 spam score, PageRank, length of url 等，与上面的算法结合可以综合评估网页的分数。

VSM

假设文档 d 对应的向量用 $\overrightarrow {V}(d)$ 表示，每个维度对应一个 term，向量分量一般可以采用 tf-idf 权重计算方式。一组文档的集合看作向量空间的多个向量，每个 term 对应一个坐标轴，然后在向量空间下进行相似度计算。

思想

文档与查询都是高维空间中的一个向量

文档是词语组成的向量
词语是文档组成的向量
查询是词语组成的向量

相似度计算

相似度的计算方法。

Inner product
Dice coefficient
Jackard coefficient
Cosine correlation

余弦相似度 (cosine similarity)

直接向量差(overlap measures)衡量相似度会产生下面的问题，

并没有对向量长度进行归一化
所有的 term 都被看作是同等重要的

可能导致的结果是，两篇内容相似的文档向量的差向量可能很大，因为一篇文档可能比另一篇文档长很多。

最常用的 similarity metric 还是 cosine similarity.

关于 Vector Coefficient 我们需要考虑以下三点：

Document term weight: 文档中每个 term 的重要性 ==> tf -> log(tf+1)
Collection term weight: 文档集合中每个 term 的重要性 ==> idf -> $log{N \over df}+1$ (avoid idf=0)
Length normalization: 对文档长度进行的补偿

关于文档长度：

长文档由于更可能包含匹配词语，因而更可能相关
然而，如果两篇文档具有同样的相似值，用户更倾向于短文档，短文档更聚焦在用户信息需求上
因此相似性计算中应该考虑文档长度(进行规范化)

更进一步的 cosine-similarity，Inc.ltc

这个公式可以用作 #SUM 的计算，仅计算包含了查询词的文档的分数。

Length Bias

大多数的 similarity metrics 都会有一个 length bias，就是说短文档的分数被高估了，长文档的分数被低估了，

所以我们需要 pivote document length normalization，可以采用 Lnu.Ltu metric.

Lucene 应用

Lucene 的检索过程：

使用布尔查询检索到一个文档集合
用 VSM 算法来对这个集合对文档进行排序

Simplified Lucene’s tf.idf Ranker

与 Inc.ltc 的不同

tf weight 用了 sqrt(tf) 而不是 log(tf)+1，stronger reward for frequent terms in document
idf weight 用了 square 而不是 idf，stronger penalty for frequent terms across corpus

小结

Key idea: Measure similarity among weighted term vectors

Vector Space Retrieval Model 没有告诉我们怎么 set term weights，没有告诉我们怎么确定 similarity，也没有告诉我们怎么支持 query-independent weights，它的优点是灵活，缺点也是灵活，所有的东西都要我们自己设置。

Okapi BM25

BM25 十分重视 term frequency 和 document length，这里省略了公式推导过程，直接分析参数。

k1

如果 k1 取 0，则对应 BIM 模型，document term frequency 完全没有影响，rare word (idf)和 repeated query terms(query tf) dominate；如果 k1 取较大值，对应使用原始的 term frequency。

b

b (0<=b<1) 决定文档的缩放长度：b=1 表示基于文档长度对 term frequency 进行完全的缩放，b=0 表示归一化时不考虑文档长度因素，长文档更有可能排在前面。

k3

如果查询很长，对于 query term 也可以采用类似的权重计算方法。对查询长度没有进行归一化（相当于b=0）。k3=0 表示 term frequency in query 并没有影响，(apple apple pie) 和 (apple pie) 完全一样。
这一项通常是由用户确定的，对应的 operator 是 $WSUM

参数优化

整个公式的参数可以通过在单独的开发测试集上搜索最优参数来最大化检索性能，如网格搜索方法（grid search）。现有的试验中，参数的合理取值范围是 k1,k3 取 1.2~2，b 取 0.75。

除了对用户查询提供 term frequency 计算方法外，在相关反馈中还可以考虑查询扩展，在已知的相关文档利用公式对 term 进行排序，并选取最靠前的多个 term 构成新的查询，再进行计算。

RSJ weight

RSJ weight 和 idf 相似，都 favor rare words in corpus，因为 rare words 能更好的区分相关文档与不相关文档。RSJ 也有不足的地方。
如果 df=N/2，那么 RSJ weight 就会变成 log(1)=0，匹配一个 term 对文档分数没有任何影响。
如果 df>N/2，RSJ weight=log(fraction)<0，匹配一个经常出现的 term 会降低文档分数。

通常的解决方案是，把 RSJ weight 设置成 $Max(0，log{N-df+0.5 \over df+0.5})$。如果我们用 idf 公式代替 RSJ weight，那么对 frequent words 的惩罚就会减小，尤其是对那些出现了 N/2 的词。

最近，Lucene 转变了 ranking 算法，变成了 BM25 Ranker

Summary

优点：

有很强的概率理论支持
在新的环境中参数可以被调整
在大量的 evalution 中都非常有效

缺点：

经验调整参数

Query Likelihood

假定四个变量

d: document
$\theta_d$: language model for document d
q: query
$\theta_q$: language model for query q

q 和 $\theta_q$，d 和 $\theta_d$ 不是同一个东西，然而为了方便表示，我们就用 q 直接表示，p(d|q) 代替 p(d|$\theta_q$)

我们生成两个模型，一个是 document 的语言模型，一个是 query 的语言模型，有两种方案来对文档进行排序

Rank d by $p(d|\theta_q)$ (query likelihood)
Rank d by similarity of $\theta_d$ and $\theta_q$ (KL divergence)

Rank by P(d|q)

给定一个 query，出现文档 d 的概率，query 一般很短，$\theta_q$ 非常的稀疏，它包含了很少的 term frequency 信息，所以我们用 Bayes rule 来转换它。

$p(d|q)={p(q|d)p(d) \over p(q)}$
–> 丢掉 document-independent term
$p(q|d)p(d)$
–> 丢掉 constant term
$p(q|d)$
–>
$\prod p(q_i|d)$

于是问题就变成了怎么估计 $p(q_i|d)$

$p(q_i|d)$

我们用最大似然 (Maximum likelihood estimation MLE)。
$$P_{MLE}(q_i|d)={tf_{q_i,d} \over length(d)}$$

是一个好的估计吗？
首先它基于一篇文档，所以结果可能没那么准确，如果 document 里没有出现 $q_i$，那么结果就是 0，这相当于一个 boolean AND，所以 $q_i$ 是对 document 的一个不错的描述，即使它不在 document 中。

所以我们要用 smoothing，来提高 MLE 的准确性，同时来预测没有出现过的词。

Smoothing

Jelinek-Mercer(“Mixture Model”) Smoothing

$$p(q_i|d)=(1-\lambda)p_{MLE}(q_i|d)+ \lambda p_{MLE}(q_i|C)$$

C 代表整个 collection，$\lambda$ 越小，smoothing 的作用越小，越适合短 query，$\lambda$ 越大，smoothing 的作用越大，越适合长 query。为什么？对短文档而言，通常每一个 query term 都要匹配，所以 idf weighting 并没有那么重要，越小的 smoothing 越好，而对于长 query 而言，大部分 query term 必须匹配，而另一部分可以不 match，所以 idf weighting 会更重要，就可以多 smoothing 一点。

Jelinek-Mercer smoothing 的作用与 idf 类似，它能够区分文档集合里常见的和不常见的 term 。

看一个具体例子，有两个 query term，一个 frequent 一个 rare。

p(apple|C)=0.01, p(ipod|C)=0.001

两篇文档

doc1: doclen=50,$tf\_{apple}=2$,$tf\_{ipod}=3$
doc2: doclen=50,$tf\_{apple}=3$,$tf\_{ipod}=2$

没有 smoothing 前，两篇文档的 p(q|d)都是 0.0024

2/50 ＊ 3/50=0.0024
3/50 ＊ 2/50=0.0024

JM Smooth 后，假设 $\lambda=0.4$

doc1: p(q|d)=(0.6* 2/50 + 0.4*0.01) * (0.6 * 3/50 + 0.4*0.001)=0.001019
doc2: p(q|d)=(0.6* 3/50 + 0.4*0.01) * (0.6 * 2/50 + 0.4*0.001)=0.000976

这就发现，smooth 能够区分文档集合里常见的和不常见的 term。
我们也可以计算 doclen=50,$tf_{apple}=2$,$tf_{ipod}=2$ 的情况，看多加入一个 apple 或 ipod 后 p(q|d) 发生了什么，同样的，unsmoothed effect 对常见的和不常见的 term 并没有差别，但是 smooth 带来了显著差异。

最后上张推导图

Bayesian Smoothing With Dirichlet Priors

$$p(q_i|d)={tf_{q_i,d}+ \mu p_{MLE}(q_i|C) \over length(d)+ \mu }$$

$\mu$ 在 [1000-10000] 区间内比较好
Bayesian smoothing 是对文档长度的平滑，对短文档而言，$p(q_i|d)$ 的概率分布更不平滑，需要更大的 $\mu $，对长文档而言，概率分布更平滑，需要更小的 $\mu$.

Two-Stage Smoothing

可以结合以上两种平滑方式，得到
$$p(q_i|d)=(1- \lambda ){tf_{q_i,d}+ \mu p_{MLE}(q_i|C) \over length(d)+ \mu }+ \lambda p_{MLE}(q_i|C)$$

Rank by similarity

KL Divergence
Kullback-Leibler 距离，也叫相对熵（Relative Entropy）。计算公式如下：
$$KL(p||q)=\sum p(x)log{p(x) \over q(x)}$$

KL 距离不是对称的, KL(p||q)!=KL(q||p)，我们要计算的是 KL(q||d)，query 和 document 的相对熵，推导公式如下。

Comparsion

两种方式其实是一样的，仔细看公式！
Query likelihood ranks by
$$p(q|d)=\prod p(q_i|d)$$

KL diverge ranks by
$$\sum p(x)log{p(x) \over q(x)}$$

Inference networks(Indri)

document + smoothing parameter($\alpha$ $\beta$) -> language model($\theta$) -> language model vocabulary(r)

information needs(I)由 query(q) 表示，query 由 operator(c) 组成.

在 Indri 中，#AND 认为所有的 argument 都是独立概率， #WSUM 认为所有的 argument 都用来估计同一个概率。
在实现 Indri 的 ranking algorithm 时，要注意的是我们必须实现一个 getDefaultScore，来处理 tf=0 的情况，以保证用户总能得到搜索结果。

Document Priors

Document Priors 指与 query 无关的用来评估文档价值的 estimates (query-independent estimates of the value of each document)，一般是根据文档本身的性质来决定的，主要的 document priors 有 spam score, PageRank, length of url 等。
在 BM25，query likelihood 和 KL divergence 中的使用。

Indri 中，prior 在 Query likelihood 中的表示为 #and(#prior(url) a b c)，在 KL divergence 中的表示为 #and(#prior(url) #and(a b c))